public class TestBinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val=val;
        }
    }
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;

        return A;
    }
    public void preOrder (TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        //递归遍历左子树
        preOrder(root.left);
        //递归遍历右子树
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //求整个树的节点个数
    public int size(TreeNode root){
        if(root==null){
            return 0;
        }
        int ret=size(root.left)+size(root.right)+1;
        return ret;
    }
    //遍历思路
    public int nodeSize;
    public void size2(TreeNode root){
        if(root==null){
            return;
        }
        nodeSize++;
        size2(root.right);
        size2(root.left);
    }
    public int getLeafNodeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    //遍历思路
    public int leafSize;
    public void getLeafNodeCount2(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

    //求第K层的节点个数 K默认是一个合法的
    public int getKLeveNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLeveNodeCount(root.left,k-1)+getKLeveNodeCount(root.right,k-1);
    }
    //求树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
//        return Math.max(leftHeight,rightHeight)+1;
        return leftHeight>rightHeight?
                leftHeight+1:rightHeight+1;
    }
//    找值为val的节点
    public TreeNode find(TreeNode root ,int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=root.left;
        if(ret!=null){
            return ret;
        }
        ret=root.right;
        if(ret!=null){
            return ret;
        }
        return null;
    }
    //判断两棵树是否相同 时间复杂度是O(min(m,n))
    public boolean isSameTree (TreeNode p,TreeNode q){
        //1.结构不一样，一个为空，一个不为空
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        //2.两个都为空
        if(p==null&&q==null){
            return true;
        }
        //3.两个都不为空，值不一样
        if(p.val!=q.val){
            return false;
        }
        //4.此时根节点一样，要判断左子树是否一样和右子树是否一样
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.left);
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int leftH=maxDepth(root.left);
        int rightH=maxDepth(root.right);

        return Math.abs(leftH-rightH)<=1
                &&isBalanced(root.left)
                &&isBalanced(root.right);
    }
    public int maxDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftH=maxDepth(root.left);
        int rightH=maxDepth(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }

    public boolean isBalanced2(TreeNode root) {
        if(root==null) return true;
        return maxDepth(root)>=1;
    }
    public int maxDepth2(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftH=maxDepth(root.left);
        if(leftH<0){
            return -1;
        }
        int rightH=maxDepth(root.right);
        if(rightH<0){
            return -1;
        }
        if(Math.abs(leftH-rightH)<=1){
            return leftH>rightH?leftH+1:rightH+1;
        }else{
            return -1;
        }

    }

}
